package tree.tree2.symmetry.Path;

import tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName hasPathSum
 * @Description TODO
 * @Author lenovo
 * @Date 2023-05-04 10:23
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class hasPathSum {

    /**
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     * <p>
     * 说明: 叶子节点是指没有子节点的节点。
     * <p>
     * 示例: 给定如下二叉树，以及目标和 sum = 22，
     */

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    public boolean hasPathSum1(TreeNode root, int targetSum) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> queueSum = new LinkedList<>();
        queue.add(root);
        queueSum.add(root.val);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode poll = queue.poll();
                Integer poll1 = queueSum.poll();
                if (poll.left == null && poll.right == null) {
                    return poll1==targetSum;
                }
                if (poll.left != null) {
                    queue.add(poll.left);
                    queueSum.add(poll1 + poll.left.val);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                    queueSum.add(poll1 + poll.right.val);
                }
                size--;
            }
        }
        return false;
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(20);
        treeNode.left = new TreeNode(2);
        hasPathSum hasPathSum = new hasPathSum();
        System.out.println(hasPathSum.hasPathSum1(treeNode, 22));
    }
}